USACO 2023 US Open Contest, Bronze

[USACO23OPEN] FEB

题目描述

贝西和埃尔希正在密谋最终推翻他们的主人——农夫约翰！他们通过 $N$ 条短信进行计划。他们的对话可以用一个长度为 $N$ 的字符串 $S$ 来表示。

其中 $S_{i}$ 是字母 B 或 E，这意味着第 $i$ 条消息分别由贝西或埃尔希发送的。

然而，农夫约翰听说了这个消息，并试图拦截他们的谈话。因此，字符串 $S$ 的一些字母是 F，这意味着农夫约翰混淆了信息，发件人未知（贝西、埃尔希都有可能）。

注：约翰没有发送信息！他只是在干扰奶牛间的通话！*

未混淆对话的兴奋程度是一只奶牛重复发送信息的次数。也就是说，子串 BB 或 EE 在 $S$ 中出现的次数。你想找到原始信息的兴奋程度，但你不知道约翰的信息中哪一条实际上是贝西或埃尔希的。在所有可能的情况下，从小到大输出所有可能的兴奋程度。

输入格式

第一行：一个整数 $N$ （通话长度）。

第二行：一个字符串 $S$ （通话内容）。

输出格式

第一行：输出一个整数 $K$ ，为不同兴奋程度的可能数量。

随后 $K$ 行：每行一个整数，为每种兴奋程度。注意按照从小到大的顺序输出。

输入输出样例 #1

输入 #1

4
BEEF

输出 #1

2
1
2

输入输出样例 #2

输入 #2

9
FEBFEBFEB

输出 #2

2
2
3

输入输出样例 #3

输入 #3

10
BFFFFFEBFE

输出 #3

说明/提示

$1 \leq N \leq 2 \times 10^{5}$ 。

测试点 4~8： $N \leq 10$
测试点 9~20：无额外限制。

解题思路

分讨+思维题。

以下我们设 B 为 0，E 为 1，F 为 x。那么可以随便写一个一般的样例，比如：xxx01xxx0010xxxx011。于是答案就是所有含 x 段的价值之和。

观察这个样例，我们发现：一共有三种可能的 x...x 段：

两边都没有确定的取值。
只有一边有确定的取值，比如第一段。
左右都有确定的取值，比如上面的第二段和第三段。

那么一个自然的想法产生了：既然要算所有的段的价值之和，我们可以分这三种情况，把每种情况的价值都表示出来，再合并它们。

Step 1:

我们先挑最简单的情况，也就是情况 1 下手。

如果存在这种段，那就意味着整个串是 xxxxxxx 的形式。不妨设一共有 k 个 x，那一共就有 k 个答案，并且答案从 0 到 k−1 都有可能。

为什么呢？因为这个串可以是 0101010，0101011，0101000，0101111，0100000，0111111 以及 0000000。答案分别是 0 到 k−1。

这种情况特判即可。

Step 2:

接下来讨论情况 2。

不妨设这种段为 0xxxxxx，其中有 k 个 x。容易想到，这种段等价于 xxxxxx0，因为可以对称得到；同时它也等价于 1xxxxxx，因为可以取反得到。

举例：0111011 可以对称得到 1101110 ，也可以取反得到 1000100。它们对答案贡献的数量相同。

那么每个这种段可以贡献多少种答案呢？和情况 1 相同，我们发现最多可以取全是 0，答案为 k。以此类推（建议读者自己再推推看），发现答案分别是 0 到 k。

即每个情况 2 贡献的价值集合是从 0 到 k，公差为 1 的等差数列。

Step 3:

最后要攻克情况 3 了。

这种情况比较复杂，因为它又细分为两种情况：左右取相同和左右取不同。

先看取相同。

同情况 2，我们设这种段为 0xxxxx0，其中有 k 个 x。当然，它和左右都取 1 也是一样的。

那么来看这种情况。假设 k=5，那么最多可取 0000000，答案为 6，也就是 k+1。最少可取 0101010，答案为 0。

这里以下是重点！！！ 我们发现 k 取 6 的话，最少为 01010100，就只能取 1 而不是 0 了！也就是说，如果 k+1 是偶数的话，答案最少取到 0；反之最少取到 1。

好，最多最少都有了，那么中间的每一个值能否都取到呢？

这里我们来采用一种简单而有效的方式分析:

假设一段一般的情况 3 为 0110100010，我们考虑改动其中一位对最终答案的影响。

修改第二位，则它的左边加一，右边减一。（0 0 10100010）
修改第三位，则它的左边减一，右边加一。（01 0 0100010）
修改第五位，它的则左右都加一。（0110 0 00010）
修改第七位，则它的左右都减一。（011010 1 010）

好，我们发现，修改一位对答案的影响是增加 2 或减少 2。

那所有可能的价值就是：k+1,k+1−2,k+1−4,…,0/1。

即当 k+1 为偶数时，情况 3（左右取相同）贡献的价值集合是从 0 到 k+1，公差为 2 的等差数列；反之，贡献的价值集合是从 1 到 k+1，公差为 2 的等差数列。

再看取不同。

同样地，我们设这种段为 0xxxxx1，其中有 k 个 x。当然，它和左边取 1，右边取 0 也是一样的。

同上，我们经过简单的推导可知，答案最多取 k（0000001），当 k 为偶数时，最少取 0（01010101）；反之，最少取 1（0101011）。

我们用同样的方法分析得到，所有可能的价值就是：k,k−2,k−4,…,0/1。

即当 k 为偶数时，情况 3（左右取不同）贡献的价值集合是从 0 到 k，公差为 2 的等差数列；反之，贡献的价值集合是从 1 到 k，公差为 2 的等差数列。

Step 4:

好，看到这里并自己分析一遍的读者可以喘口气了，我们已经把每种段的取值情况都分析完毕了。接下来的任务是：把所有的段加到一块，所有可能的取值有哪些！

先看中间的段（即情况 3）。

因为中间的段的取值都对应一个公差为 2 的等差数列。

我们举一个例子：1,3,5 和 2,4,6,8。这两个数列合并后的取值有哪些？手玩可以得出 3,5,7,…,13。刚好是首项为 1+2，末项为 5+8，公差为 2 的等差数列！

当然对于两个一般的序列 a 和 b，也是一样的：

![img](./USACO 2023年3月铜牌.assets/lhmrlx0q.png)

因为公差相同，所以最终得出的数列刚好是 a1+b1,a2+b1,…,a**n+b1,a**n+b2,a**n+b3,…,a**n+b**m，而且公差也是 2！

所以要计算中间的段的总贡献，我们只需要计算每一段可取的最小值之和，以及每一段可取的最大值之和就行了！

再看两边的段（即情况 2）。

同样地，我们得出两个公差为 1 的等差数列合并，仍然得到一个公差为 1 的等差数列。

现在把上面两种情况加起来。

同样地，我们可以举一个例子：2,4,6,8 和 1,2,3。现在考虑合并它们。

使用小学奥数的凑数法，得出 3,4,5,…,11。

所以一个公差为 1 的等差数列和一个公差为 2 的等差数列合并，得到一个公差为 1 的等差数列。

所以最终做法就有了：

先求中间的段可以得到的最大值（即每一个 x 都和它前面一位取相同值时）和最小值（即每一个 x 都和它前面一位取不同值时）。
再求两边的段可以得到的最大值（如果两边有段的话）。比如最开头的例子 xxx01xxx0010xxxx011，数一下两边的 x 的个数 k 即可。
合并 1 和 2。

示例代码

c++

#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	string s;
	cin >> n >> s;
	//特判情况1
	if (s == string(n, 'F')){
		cout << n << '\n';
		for (int i = 0; i < n; i ++ )
			cout << i << '\n';
		return 0;
	}
	//求中间
	int l = 0, r = n - 1;
	while (s[l] == 'F') 
		l ++;
	while (s[r] == 'F') 
		r --;//排除两边的x，l和r是中间段和两边段的分界点
	int low = 0, high = 0;//分别是可以取到的最小值和最大值
	//先算最小值
	string t = s;
	for (int i = l; i <= r; i ++ ){
		if (t[i] == 'F'){//每一个x都取不同值
			if (t[i - 1] == 'B') 
				t[i] = 'E';
			else t[i] = 'B';
		}
		if (i > l && t[i] == t[i - 1])//l是边界，不能计入答案
			low ++;
	}
	//再算最大值
	t = s;
	for (int i = l; i <= r; i ++ ){
		if (t[i] == 'F')//每一个x都取相同值
			t[i] = t[i - 1];
		if (i > l && t[i] == t[i - 1]) 
			high ++;
	}
	int lb = l + n - 1 - r, d = 2;//lb是两边的最大值，即0~l-1和r+1~n-1。d是公差。
	if (lb) //两边存在，则合并，公差变为1
		high += lb, d = 1;
	cout << (high - low) / d + 1 << '\n';
	for (int i = low; i <= high; i += d )
		cout << i << '\n';
	return 0;
}

[USACO23OPEN] Moo Language B

题目描述

题目背景

FJ 对与奶牛更好地互动感兴趣，所以他决定学习 moo 语言！

moo 语言与英语相似，但更为简单。单词只有四种类型：名词、及物动词、不及物动词和连词，每两个单词之间必须用空格隔开。标点符号仅包含逗号和句号，它会跟在单词后面，若该标点符号后面存在单词，则需要隔一个空格再放单词。

对于每个句子，都需要遵循以下格式中的一条：

名词+不及物动词。
名词+及物动词+名词（可以有多个）。及物动词后面必须有至少一个名词。除及物动词后面的第一个名词外，后面的每个名词前面都必须加一个逗号。

也可以在两个句子之间加一个连词，形成复合句，复合句不能与其他句子用连词连接。每一个句子（包括复合句）都必须以句号结尾。

FJ 的词库中有 $N$ 个单词、 $C$ 个逗号和 $P$ 个句号。每个单词的使用次数不能超过这个单词在词库中出现的次数。现在，你要帮他输出几个符合以上要求的句子，使总单词数尽量多。

每个输入文件中共包含 $T$ 组样例。

输入格式

第一行输入 $T$ ，表示样例组数。对于每组样例，格式如下：

第一行输入三个正整数 $N$ 、 $C$ 和 $P$ 。

在接下来的 $N$ 行，每行输入两个字符串。第一个字符串输入一个 FJ 可以用的单词（全为小写字母，长度为 $1$ 至 $10$ ），第二个字符串为以下字符串中的任意一个，表示该单词的类型：

noun（名词）；
transitive-verb（及物动词）；
intransitive-verb（不及物动词）；
conjunction（连词）。

同一个单词可能在词库中出现多次，但是每次出现时它们的类型都相同。

输出格式

第一行输出组成符合以上要求的句子序列的最大单词数。

在第二行中，输出句子序列，使单词数最多。本题开启 SPJ，任何符合以上要求的句子序列均可通过。

请不要输出多余的空格，尤其是在每行末尾。

输入输出样例 #1

输入 #1

3
1 1 1
bessie noun
10 5 4
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
24 5 4
but conjunction
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
bob noun
impressed transitive-verb
cow noun
impressed transitive-verb
leaped intransitive-verb
elsie noun
bella noun
buttercup noun
pushed transitive-verb
mooed intransitive-verb
envy noun
john noun
nhoj noun

输出 #1

0

9
nhoj mooed. farmer taught elsie, bessie and john flew.
23
nhoj mooed. nhoj impressed john, farmer, elsie, bessie and cow impressed bob. bella pushed elsie and buttercup flew. envy mooed but john leaped.

说明/提示

$1 \leq T \leq 100$ ， $1 \leq P, C \leq N \leq 10^{3}$ 。

输入 2-6： $N \leq 10$ 。
输入 7-11： $N \leq 100$ 。
输入 12-16： $N \leq 1000$ 。
输入编号除以 5 余 2 的测试点：没有及物动词。
输入编号除以 5 余 3 的测试点：没有不及物动词。
输入编号除以 5 余 4 的测试点：没有连词。

分析

输入解析：
- 单词数量 N=10。
- 逗号数量 C=5。
- 句号数量 P=4。
- 单词及其类型：
  - 名词：bessie, elsie, farmer, john, nhoj
  - 及物动词：taught
  - 不及物动词：flew, mooed
  - 连词：and（2个）
句子构造：
- 句子总数：s=P+min(P,连词数量)=4+min(4,2)=6。
- 构造句子：
  1. 优先构造不及物动词句子：
    - nhoj mooed（名词 + 不及物动词）
    - john flew（名词 + 不及物动词）
  2. 构造及物动词句子：
    - farmer taught elsie, bessie and john（名词 + 及物动词 + 名词 + 名词 + 名词）
  3. 使用连词连接句子：
    - nhoj mooed. farmer taught elsie, bessie and john flew.
输出解释：
- 最大单词数为 9。
- 输出的句子为：
```
nhoj mooed. farmer taught elsie, bessie and john flew.
```
  1
- 这里使用了 3 个名词、2 个不及物动词、1 个及物动词和 2 个连词，共 9 个单词。

解题思路

逗号必定和名词放一起
连词要尽量多使用
先计算语句的总数（尽量多)，设 s 为句子的总数量， o 为连词数。 s=p+min(p,o)
先尽量多的用不及物动词
在尽量多的用及物动词
由于使用及物动词可以多消耗名词，所以尽量将不及物动词语句替换成及物动词的句子
由于逗号可以和名词一一搭配，所以把他们加入一个及物动词语句内。
统计词数，输出所有语句（记得加上连词）

代码示例

c++

#include <bits/stdc++.h>

using namespace std;

const int N = 2005;

int t, n, c, p, sum, h, l;

vector<string> a[5], ans[N];  // 0 名词，1 连词，2 及物动词，3 不及物动词，4 用于临时存储句子

int main() {
    // 外层循环处理多组测试数据
    for (cin >> t; t; t--, sum = h = l = 0) {
        cin >> n >> c >> p;  // 输入单词数量、逗号数量和句号数量
        // 清空每种类型单词的存储容器
        for (int i = 0; i < 4; i++) {
            a[i].clear();
        }
        // 读取单词及其类型
        for (int i = 1, o; i <= n; i++) {
            string s, t;
            cin >> s >> t;
            if (t[0] == 'n') {
                o = 0;  // 名词
            } else if (t[0] == 'c') {
                o = 1;  // 连词
            } else if (t[0] == 't') {
                o = 2;  // 及物动词
            } else {
                o = 3;  // 不及物动词
            }
            a[o].push_back(s);  // 将单词存入对应类型的容器
        }
        // 计算句子总数，考虑连词的使用
        p = p + min(p, (int)a[1].size());  // 句子数 = 句号数量 + 最多可以使用的连词数量
        // 尽量多构造不及物动词句子
        for (; a[0].size() && a[3].size() && h < p; sum += 2) {  
            ans[++h] = a[4];  // 初始化句子容器
            ans[h].push_back(a[0].back()), ans[h].push_back(a[3].back());  // 添加名词和不及物动词
            a[3].pop_back(), a[0].pop_back();  // 使用过的单词从容器中移除
        }
        l = h;
        // 尽量多构造及物动词句子
        for (; a[0].size() >= 2 && a[2].size() && h < p; sum += 3) { 
            ans[++h] = a[4];  // 初始化句子容器
            ans[h].push_back(a[0].back()), ans[h].push_back(a[2].back());  // 添加名词和及物动词
            a[2].pop_back(), a[0].pop_back();  // 使用过的单词从容器中移除
            ans[h].push_back(a[0].back()), a[0].pop_back();  // 添加及物动词后的名词
        }
        // 尝试将不及物动词句子替换为及物动词句子，当前还有多的及物动词和名词。
        for (; l && a[0].size() && a[2].size(); l--, sum++) {
            ans[l].pop_back();  // 移除不及物动词
            ans[l].push_back(a[2].back()), ans[l].push_back(a[0].back());  // 替换为及物动词和名词
            a[0].pop_back(), a[2].pop_back();  // 使用过的单词从容器中移除
        }
        // 在及物动词句子中加入尽可能多的名词和逗号
        for (; l != h && a[0].size() && c; c--, sum++) {
            ans[h].push_back(a[0].back()), a[0].pop_back();  // 添加名词
        }
        // 输出单词总数和构造的句子
        cout << sum + min(h / 2, (int)a[1].size()) << '\n';  // 单词总数 = 当前单词数 + 可以使用的连词数量
        for (int i = 1; i <= h; i++) {
            for (int j = 0; j < ans[i].size(); j++) {
                if (j > 2) {
                    cout << ",";  // 在及物动词句子中，名词之间用逗号分隔
                }  
                if (j) {
                    cout << " ";  // 单词之间用空格分隔
                }
                cout << ans[i][j];  // 输出单词
            }
            if (i < h) {  // 如果还有句子
                if (i % 2 && a[1].size()) {  // 还可以使用连词，而i % 2 的作用是判断当前句子编号是否为奇数，从而决定是否可以使用连词连接到下一个句子。如果是偶数就代表与上一个句子进行连接了。
                    cout << ' ' << a[1].back() << ' ';
                    a[1].pop_back();  // 使用过的连词从容器中移除
                } else {
                    cout << ". ";  // 不然输出句号
                }
            }
        }
        if (sum) {
            cout << "." << "\n";  // 最后一个句子输出句号
        }
    }
    return 0;
}

[USACO23OPEN] Rotate and Shift B

题目描述

注意：本题的时间限制为 4 秒，是默认时间限制的 2 倍。

为了庆祝春天的到来，Farmer John 的 $N$ 头奶牛发明了一种有趣的舞蹈，她们围成一个圆圈，并以一种可预测的方式重新排列自己。

具体来说，圆圈上有 $N$ 个位置，编号从 $0$ 到 $N - 1$ ，其中位置 $0$ 紧接着位置 $N - 1$ 。每个位置上有一头奶牛。奶牛的编号也从 $0$ 到 $N - 1$ 。初始时，奶牛 $i$ 位于位置 $i$ 。你会被告知一组 $K$ 个“活跃”位置 $0 = A_{1} < A_{2} < \dots < A_{K} < N$ ，这意味着这些位置上的奶牛是下一批要移动的。

在舞蹈的每一分钟，会发生两件事。首先，活跃位置上的奶牛会旋转：位置 $A_{1}$ 的奶牛移动到位置 $A_{2}$ ，位置 $A_{2}$ 的奶牛移动到位置 $A_{3}$ ，依此类推，位置 $A_{K}$ 的奶牛移动到位置 $A_{1}$ 。所有这些 $K$ 次移动同时发生，因此在旋转完成后，所有活跃位置仍然恰好有一头奶牛。接下来，活跃位置本身会移动： $A_{1}$ 变为 $A_{1} + 1$ ， $A_{2}$ 变为 $A_{2} + 1$ ，依此类推（如果某个活跃位置 $A_{i} = N - 1$ ，则 $A_{i}$ 会循环回到 $0$ ）。

请计算舞蹈进行 $T$ 分钟后奶牛的顺序。

输入格式

第一行包含三个整数 $N$ 、 $K$ 和 $T$ 。

第二行包含 $K$ 个整数，表示初始的活跃位置 $A_{1}, A_{2}, \dots, A_{K}$ 。注意 $A_{1} = 0$ ，并且这些位置是按递增顺序给出的。

输出格式

输出 $T$ 分钟后奶牛的顺序，从位置 $0$ 的奶牛开始，用空格分隔。

输入输出样例 #1

输入 #1

5 3 4
0 2 3

输出 #1

1 2 3 4 0

说明/提示

对于上述样例，以下是前四个时间步的奶牛顺序和活跃位置 $A$ ：

初始，T = 0：顺序 = [0 1 2 3 4]，A = [0 2 3]
T = 1：顺序 = [3 1 0 2 4]
T = 1：A = [1 3 4]
T = 2：顺序 = [3 4 0 1 2]
T = 2：A = [2 4 0]
T = 3：顺序 = [2 4 3 1 0]
T = 3：A = [3 0 1]
T = 4：顺序 = [1 2 3 4 0]

$1 \leq K \leq N \leq 2 \cdot 10^{5}$ ， $1 \leq T \leq 10^{9}$ 。

输入 2-7： $N \leq 1000$ ， $T \leq 10000$ 。
输入 8-13：没有额外限制。

解题思路

环形表示：通过设置a[k]=a[0]+n，将环形结构表示出来，便于计算。
双指针技术：通过j+=a[j]<=i找到每个位置i左边最近的活跃位置j。这是一个巧妙的更新方式，当当前活跃位置小于等于i时，j向后移动。
周期计算：
- d=a[j]-a[j-1]计算相邻两个活跃位置之间的距离，这个距离就是一个完整周期。
- 位置i上的元素会在第一次被活跃位置影响后，每过d分钟就会被向右移动d个位置。
1. 核心公式：b[(i+((t-i)+a[j]-1)/d*d)%n]=i
- (t-i)表示从位置i开始，还要经过多少分钟
- (t-i)+a[j]-1)/d计算完整周期数
- 乘以d得到总位移距离
- 加上i是初始位置
- 最后取模n保证在0到n-1范围内

示例代码

c++

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=2e5+5; // 根据题目约束，N最大为2*10^5
ll n,k,t;
ll a[N],b[N],d;

int main(){
    // 读取输入：位置总数n，活跃位置数量k，舞蹈进行的分钟数t
    scanf("%lld%lld%lld",&n,&k,&t);
    
    // 读取k个活跃位置
    for(int i=0;i<k;i++){
        scanf("%lld",&a[i]);
    }
    
    // 将环形结构表示出来，便于计算
    a[k]=a[0]+n;
    
    // 双指针技术，枚举每个位置
    for(int i=0,j=0;i<n;i++){
        // 更新j指针，找到当前位置i左边最近的活跃位置
        j+=a[j]<=i;
        
        // 计算周期长度：相邻两个活跃位置之间的距离
        d=a[j]-a[j-1];
        
        // 核心计算公式，确定i位置的元素在t分钟后的新位置
        // (t-i)表示从位置i开始，还要经过多少分钟
        // (t-i)+a[j]-1)/d计算完整周期数
        // 乘以d得到总位移距离
        // 加上i是初始位置
        // 最后取模n保证在0到n-1范围内
        b[(i+((t-i)+a[j]-1)/d*d)%n]=i;
    }
    
    // 输出最终位置上的奶牛编号
    for(int i=0;i<n;i++){
        cout<<b[i]<<" ";
    }
    
    return 0;
}

USACO 2023 US Open Contest, Bronze ​

[USACO23OPEN] FEB ​

题目描述 ​

输入格式 ​

输出格式 ​

输入输出样例 #1 ​

输入 #1 ​

输出 #1 ​

输入输出样例 #2 ​

输入 #2 ​

输出 #2 ​

输入输出样例 #3 ​

输入 #3 ​

输出 #3 ​

说明/提示 ​

解题思路 ​

Step 1: ​

Step 2: ​

Step 3: ​

Step 4: ​

示例代码 ​

[USACO23OPEN] Moo Language B ​

题目描述 ​

题目背景 ​

输入格式 ​

输出格式 ​

输入输出样例 #1 ​

输入 #1 ​

输出 #1 ​

说明/提示 ​

分析 ​

解题思路 ​

代码示例 ​

[USACO23OPEN] Rotate and Shift B ​

题目描述 ​

输入格式 ​

输出格式 ​

输入输出样例 #1 ​

输入 #1 ​

输出 #1 ​

说明/提示 ​

解题思路 ​

示例代码 ​

USACO 2023 US Open Contest, Bronze

[USACO23OPEN] FEB

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

输入输出样例 #3

输入 #3

输出 #3

说明/提示

解题思路

Step 1:

Step 2:

Step 3:

Step 4:

示例代码

[USACO23OPEN] Moo Language B

题目描述

题目背景

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

分析

解题思路

代码示例

[USACO23OPEN] Rotate and Shift B

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

解题思路

示例代码